package com.zjj.lbw.interview.array;

/**
 * @author zhanglei.zjj
 * @description 斐波拉契数列三种解法
 * @date 2023/9/1 12:03
 */
public class Fib {
    /**
     * 暴力解法
     *
     * @param n
     * @return
     */
    public static int bf(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        return bf(n - 1) + bf(n - 2);
    }


    /**
     * 使用数组保存计算过的数值
     *
     * @param n
     * @return
     */
    public static int recursionUseArray(int n) {
        return doRecursion(new int[n + 1], n);
    }

    private static int doRecursion(int[] arr, int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (arr[n] != 0) {
            return arr[n];
        } else {
            arr[n] = doRecursion(arr, n - 1) + doRecursion(arr, n - 2);
        }

        return arr[n];
    }

    /**
     * 双指针迭代
     * @param n
     * @return
     */
    public static int recursionUseDoubleIndex(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        int low = 0, high = 1;
        for (int i = 2; i <= n; i++) {
            int sum = low + high;
            low = high;
            high = sum;
        }

        return high;
    }
}
